﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace EbnfStudio
{
    /**
     * EBNF grammar :
     * Syntax       = { Rule } .
     * Rule         = Identifier ({':'}"=") Expression ( "." | ";" ) .
     * Expression   = Term { Term } .
     * Term         = Factor { "|" Factor } .
     * Factor       = ε          (* empty production *)
     *              | Identifier 
     *              | Literal
     *              | Group
     *              | Optional
     *              | Repetition
     *              .
     * Identifier   = ( Letter { Letter | Digit } )
     *              | ( "<" Letter | Space { Letter | Digit | Space } ">" )
     *              .
     * Literal      = ( '"' { Character } '"' )
     *              | ( "'" { Character } "'" )
     *              .
     * Group        = "(" Expression ")" .
     * Optional     = "[" Expression "]" .
     * Repetition   = "{" Expression "}" .
     */
    public class Parser
    {

        /// <summary>
        /// Represent a lexical error
        /// </summary>
        public class ParseError : Exception
        {
            // erronous token
            public Token Token { get; set; }

            // constructor
            public ParseError(string msg, Token token) : base(msg)
            {
                this.Token = token;
            }
        }


        /// <summary>
        /// messages
        /// </summary>
        public string Output { get; private set; }

        /// <summary>
        /// The lexer object
        /// </summary>
        Lexer m_lexer = new Lexer();

        /// <summary>
        /// current and next tokens
        /// </summary>
        Token m_current, m_next;

        /// <summary>
        /// the ast syntax tree
        /// </summary>
        public AstSyntax Tree;

        /// <summary>
        /// List of tokens and associate them with
        /// Ast node
        /// </summary>
        public List<Token> Tokens = null;


        /// <summary>
        /// Reset parser state
        /// </summary>
        public void Reset()
        {
            Output = "";
            m_current = null;
            m_next = null;
            // for now...
            Tokens = new List<Token>();
        }


        /// <summary>
        /// Construct new parser object
        /// </summary>
        public Parser()
        {
            Tree = null;
            Reset();
        }


        /// <summary>
        /// Parse the input and generate the ast
        /// tree or spit out errors
        /// </summary>
        public AstSyntax Parse(string input)
        {
            // reset the state
            Reset();

            // set input
            m_lexer.Lex(new StringReader(input));

            // process
            try
            {
                Move();
                Tree = Syntax();
                return Tree;
            }
            catch (Lexer.LexicalError e)
            {
                Log(e.Line + ": " + e.Message);
            }
            catch (ParseError e)
            {
                Log(e.Token.Line + ": " + e.Message);
            }
            return null;
        }


        /// <summary>
        /// Syntax = { Rule } .
        /// </summary>
        private AstSyntax Syntax()
        {
            // rules
            List<AstRule> rules = new List<AstRule>();

            // { Rule }
            while (!Match(TokenClass.EndOfFile))
            {
                rules.Add(Rule());
            }

            // create ast node
            return new AstSyntax(rules);
        }


        /// <summary>
        /// Rule = Identifier "=" Expression ( "." | ";" ) .
        /// </summary>
        private AstRule Rule()
        {
            // Identifier
            var identifier = m_current;
            Expect(TokenClass.Identifier);

            // "="
            Expect(TokenClass.Assign);

            // Expression
            AstExpression expression = Expression();

            // ( "." | ";" )
            Expect(TokenClass.EndOfStatement);

            // generate ast node
            return new AstRule(identifier, expression);
        }


        /// <summary>
        /// Expression = Term { Term } .
        /// </summary>
        private AstExpression Expression()
        {
            // hold terminals
            List<AstTerm> terms = new List<AstTerm>();

            // Term { Term }
            while (true)
            {
                // Term
                var term = Term();

                // in Order to finish the repetition we need to check
                // for empty production ( ε ) token which is added automatically.
                // however we need clean away spurious epsilons otherwise every
                // Term will end with it.
                if (term.Factors[0] is AstEmptyFactor)
                {
                    var empty = (AstEmptyFactor)term.Factors[0];
                    if (empty.Automatic)
                    {
                        if (term.Factors.Count > 1) terms.Add(term);
                        break;
                    }
                }
                terms.Add(term);
            }

            // generate ast node
            return new AstExpression(terms);
        }


        /// <summary>
        /// Term = Factor { "|" Factor } .
        /// </summary>
        private AstTerm Term()
        {
            List<IAstFactor> factors = new List<IAstFactor>();

            // Factor
            factors.Add(Factor());

            // { "|" Factor }
            while (Accept(TokenClass.Pipe)) factors.Add(Factor());

            // generate ast node
            return new AstTerm(factors);
        }


        /// <summary>
        /// Factor  = ε             (* empty production *)
        ///         | Identifier 
        ///         | Literal
        ///         | Group
        ///         | Optional
        ///         | Repetition
        ///         .
        /// </summary>
        private IAstFactor Factor()
        {
            var token = m_current;
            switch (m_current.Id)
            {
                // ε (* empty production *)
                case TokenClass.Empty :
                    Move();
                    return new AstEmptyFactor(false);
                // Identifier
                case TokenClass.Identifier :
                    Move();
                    return new AstIdentifier(token);
                case TokenClass.Invalid :
                    Move();
                    token.Id = TokenClass.Literal;
                    return new AstLiteral(token, true);
                // Literal
                case TokenClass.Literal :
                    Move();
                    return new AstLiteral(token, false);
                // Group
                case TokenClass.Paren_Open :
                    return Group();
                // Optional
                case TokenClass.Bracket_Open :
                    return Optional();
                // Repetition
                case TokenClass.Brace_Open :
                    return Repetition();
            }

            // empty production
            return new AstEmptyFactor(true);
        }


        /// <summary>
        /// Group = "(" Expression ")" .
        /// </summary>
        private IAstFactor Group()
        {
            // "("
            Expect(TokenClass.Paren_Open);

            // Expression
            var expression = Expression();

            // ")"
            Expect(TokenClass.Paren_Close);

            // the ast
            return new AstGroup(expression);
        }


        /// <summary>
        /// Optional  = "[" Expression "]" .
        /// </summary>
        private IAstFactor Optional()
        {
            // "["
            Expect(TokenClass.Bracket_Open);

            // Expression
            var expression = Expression();

            // "]"
            Expect(TokenClass.Bracket_Close);

            // the ast
            return new AstOptional(expression);
        }


        /// <summary>
        /// Repetition = "{" Expression "}" .
        /// </summary>
        /// <returns></returns>
        private IAstFactor Repetition()
        {
            // "{"
            Expect(TokenClass.Brace_Open);

            // Expression
            var expression = Expression();

            // "}"
            Expect(TokenClass.Brace_Close);

            // the ast
            return new AstRepetition(expression);
        }


        /// <summary>
        /// Emit message
        /// </summary>
        private void Log(string msg)
        {
            // no value ?
            if (string.IsNullOrEmpty(msg)) return;

            // add new line ?
            if (Output.Length > 0) Output += "\r\n";

            // emit the msg
            Output += msg;
        }


        /// <summary>
        /// test the symbol against current
        /// </summary>
        private bool Match(TokenClass id)
        {
            return m_current.Id == id;
        }


        /// <summary>
        /// expect the symbol to be of class
        /// </summary>
        private void Expect(TokenClass id)
        {
            if (!Match(id))
            {
                string msg = "Expected '" + Token.GetClassName(id) + "'. "
                           + "Found '" + m_current.Lexeme + "'";
                throw new ParseError(msg, m_current);
            }
            Move();
        }


        /// <summary>
        /// return true and move if token id matches with the current
        /// </summary>
        private bool Accept(TokenClass id)
        {
            if (Match(id))
            {
                Move();
                return true;
            }
            return false;
        }


        /// <summary>
        /// Advance the token
        /// </summary>
        private void Move()
        {
            if (m_current == null) m_next = GetNext();
            m_current = m_next;
            m_next = GetNext(); ;
        }


        /// <summary>
        /// Read next token and filter out comments
        /// </summary>
        private Token GetNext()
        {
            var t = m_lexer.GetNext();
            Tokens.Add(t);
            while (t.Id == TokenClass.Comment)
            {
                t = m_lexer.GetNext();
                Tokens.Add(t);
            }
            return t;
        }

    }
}
